| 翻訳と辞書 |
Bull graph
In the mathematical field of graph theory, the bull graph is a planar undirected graph with 5 vertices and 5 edges, in the form of a triangle with two disjoint pendant edges.
It has chromatic number 3, chromatic index 3, radius 2, diameter 3 and girth 3. It is also a 1-vertex-connected graph and a 1-edge-connected graph.
==Bull-free graphs==
A graph is bull-free if it has no bull as an induced subgraph. The triangle-free graphs are bull-free graphs, since every bull contains a triangle. The strong perfect graph theorem was proven for bull-free graphs long before its proof for general graphs,〔.〕 and a polynomial time recognition algorithm for Bull-free perfect graphs is known.〔.〕
Maria Chudnovsky and Shmuel Safra have studied bull-free graphs more generally, showing that any such graph must have either a large clique or a large independent set,〔.〕 and developing a general structure theory for these graphs.〔.〕〔.〕〔.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Bull graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|